package object;

import java.util.Arrays;

public class Sort {
    //直接插入排序
    public static void insertSort(int[] arr) {
        if (arr == null) {
            return;
        }
        //默认区间是前闭后开，有序元素区间[0,bound),无序区间[bound，arr.length)
        //每次拿无需元素的区间的第一个元素，拿有序区间从最后一个元素从后往前遍历比较
        //以升序为例
        for ( int bound = 1; bound < arr.length; bound++) {
            int value = arr[bound];
            int cur = bound - 1;
            for (; cur >=0; cur--) {
                if (arr[cur] > value) {
                    //向后迁移移元素
                    arr[cur + 1] = arr[cur];
                } else {
                    break;
                }
            }
            arr[cur + 1] = value;
        }
    }
    //希尔排序,以升序为例
    //其实希尔排序就是直接插入排序的改良版，多进行了几次直接插入
    public static void shellSort(int[] arr) {
        if (arr == null) {
            return;
        }
        //采取长度除以2的方式更高效
        int gap = arr.length / 2;
        while (gap >= 1) {
            System.out.println("gap" + " = " + gap +": "+ Arrays.toString(arr));
            shellSortHelper(arr,gap);
            gap /= 2;
        }
    }

    private static void shellSortHelper(int[] arr, int gap) {
        if (arr == null) {
            return;
        }
        for ( int bound = gap; bound < arr.length; bound++) {
            int value = arr[bound];
            int cur = bound - gap;
            for (; cur >=0; cur -= gap) {
                if (arr[cur] < value) {
                    arr[cur + gap] = arr[cur];
                } else {
                    break;
                }
            }
            arr[cur + gap] = value;
        }
    }
    //直接选择排序
    public static void selectSort(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int bound = 0; bound < arr.length - 1; bound++) {
            for (int cur = bound + 1; cur < arr.length; cur++) {
                if (arr[cur] < arr[bound]) {
                    int tmp = arr[bound];
                    arr[bound] = arr[cur];
                    arr[cur] = tmp;
                }
            }
        }
    }
    //堆排序(升序)
    public static void heapSort(int[] arr) {
        if (arr == null) {
            return;
        }
        createHeap(arr);
        int bound = arr.length - 1;
        for (int i = 0; i < arr.length; i++) {
            int tmp = arr[0];
            arr[0] = arr[bound];
            arr[bound] = tmp;
            shiftDown(arr,bound,0);
            bound--;
        }


    }
    public static void createHeap(int[] arr) {
        if (arr == null) {
            return;
        }
        int lastNotLeaf = (arr.length - 1 - 1) / 2;
        for (int i = lastNotLeaf; i >= 0; i--) {
            shiftDown(arr,arr.length,i);
        }
    }

    private static void shiftDown(int[] arr,int length ,int index) {
        if (arr == null) {
            return;
        }
        int parent = index;
        int child = 2 * parent + 1;
        while (child < length) {
            if (child + 1 < length && arr[child + 1] > arr[child]) {
               child = child + 1;
            }
            if (arr[child] > arr[parent]) {
                int tmp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = tmp;
            } else {
                break;
            }
            parent = child;
            child = 2 * parent + 1;
        }
    }
    //冒泡排序
    public static void bubbleSort(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j +1]) {
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }
    public static void bubbleSort1(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j - 1] > arr[j]) {
                    int tmp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }


    public static void main(String[] args) {
        int[] arr = {4,2,8,10,0,6};
        //insertSort(arr);
        //shellSort(arr);
        //selectSort(arr);
        //heapSort(arr);
        bubbleSort1(arr);
        System.out.println(Arrays.toString(arr));
    }
}
